﻿// Copyright (c) 2009, Heiko Wundram (modelnine@h8me.eu).
// All rights reserved.
//
// Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following
// conditions are met:
//
// * Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.
// * Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer
//   in the documentation and/or other materials provided with the distribution.
// * Neither the name of Heiko Wundram (h8me.eu) nor the names of its contributors may be used to endorse or promote products
//   derived from this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING,
// BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT
// SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
// DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
// NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

using System;
using System.Collections.Generic;
using System.Globalization;
using System.IO;
using System.Text;
using System.Xml;

namespace eu.h8me.Parsing.ParserLib {

    /// <summary>
    /// Base class that stores a grammar description. Defining a grammar is done through a Grammar object, creating the stack
    /// machine matching the grammar, too.
    /// </summary>
    public sealed class Grammar : IEnumerable<Symbol> {

        // Constants.
        private const int START_STATE = 0;

        // Data.
        private readonly Dictionary<string, Symbol> _Symbols = new Dictionary<string, Symbol>();
        private object _Tag;
        private Symbol.MergeEventType _MergeEvent;
        private Symbol _Epsilon;
        private Symbol _EOI;
        private List<Symbol> _AugmentedSymbols;
        private Symbol _Start;
        private Dictionary<Symbol, HashSet<Symbol>> _FirstSets;
        private Dictionary<LRItemSet, int> _LRItems;
        private Dictionary<int, Dictionary<Symbol, int>> _Transitions;
        private Dictionary<int, Dictionary<Symbol, StateAction>> _States;

        /// <summary>
        /// Initialize a new, empty grammar object which has no bound terminals or non-terminals.
        /// </summary>
        public Grammar() {
            // No specific construction.
        }

        /// <summary>
        /// Access the tag of the current grammar or set it. Grammar tags may not be altered after the grammar has been
        /// finalized.
        /// </summary>
        public object Tag {
            get {
                // Return tag.
                return _Tag;
            }
            set {
                // Store tag.
                if( _States != null )
                    throw new InvalidOperationException("Trying to set tag after grammar is finalized");
                _Tag = value;
            }
        }

        /// <summary>
        /// Bind a global merge event which is called when no more specific merge event has been defined for the symbol being
        /// merged. Binding a merge event is only possible until the grammar is finished.
        /// </summary>
        public event Symbol.MergeEventType GlobalMergeEvent {
            add {
                // Attach an event if finished.
                if( _States != null )
                    throw new InvalidOperationException("Trying to attach global merge event after finish");
                else if( value == null )
                    throw new ArgumentNullException("Illegal merge event to add, is NULL");
                _MergeEvent += value;
            }
            remove {
                // Attach an event if finished.
                if( _States != null )
                    throw new InvalidOperationException("Trying to remove global merge event after finish");
                else if( value == null )
                    throw new ArgumentNullException("Illegal merge event to remove, is NULL");
                _MergeEvent -= value;
            }
        }

        /// <summary>
        /// Create a new, empty production bound to this grammar. There are no other possibilities of creating empty
        /// productions. Empty productions may not be created after the grammar has been finished.
        /// </summary>
        public Production Epsilon {
            get {
                // Create epsilon production for this grammar.
                if( _States != null )
                    throw new InvalidOperationException("Trying to create epsilon production after finish");
                return new Production(this);
            }
        }

        /// <summary>
        /// Fetch the termination symbol for this grammar (End-Of-Input). The lexer that is driven by the parser must yield this
        /// symbol after its input has ran out. The EOI symbol is only available after the grammar has been finished.
        /// </summary>
        public Symbol EOI {
            get {
                // Check whether termination symbol is created.
                if( _States == null )
                    throw new InvalidOperationException("Trying to access termination symbol before finish");
                return _EOI;
            }
        }

        /// <summary>
        /// Access the state machine that represents this grammar.
        /// </summary>
        internal Dictionary<int, Dictionary<Symbol, StateAction>> States {
            get {
                // Return state machine.
                return _States;
            }
        }

        /// <summary>
        /// Check whether the grammar has been finalized (i.e., the state machine has been constructed).
        /// </summary>
        public bool IsFinished {
            get {
                // Return state.
                return _States != null;
            }
        }

        /// <summary>
        /// Fetch the specified named grammar symbol. In case the symbol does not exist yet, create it, but only if the grammar
        /// has not been finalized yet. This is the only possibility of creating and accessing grammar symbols belonging to a
        /// grammar.
        /// </summary>
        /// <param name="name">Name of the symbol to fetch.</param>
        /// <returns>Symbol object representing this grammar symbol.</returns>
        public Symbol this[string name] {
            get {
                // Check arguments.
                if( String.IsNullOrEmpty(name) )
                    throw new ArgumentNullException("Trying to fetch grammar symbol from null name");

                // Fetch symbol from table or create it if not present.
                Symbol symb;
                if( !_Symbols.TryGetValue(name, out symb) ) {
                    // Check whether grammar is finalized.
                    if( _States != null )
                        throw new InvalidOperationException("Grammar is finalized, cannot create new symbol");
                    _Symbols[name] = symb = new Symbol(this, name);
                }

                // Return symbol.
                return symb;
            }
        }

        /// <summary>
        /// Retrieve the number of symbols that have been defined for this grammar, never including the EOI symbol.
        /// </summary>
        public int Count {
            get {
                // Return symbol count.
                return _Symbols.Count;
            }
        }

        /// <summary>
        /// Return a typed enumerator listing the symbols that are defined for this grammar.
        /// </summary>
        /// <returns>Enumerator listing the symbols defined in this grammar.</returns>
        public IEnumerator<Symbol> GetEnumerator() {
            // Return enumerator on symbols.
            return _Symbols.Values.GetEnumerator();
        }

        /// <summary>
        /// Return an untyped enumerator listing the symbols defined for this grammar.
        /// </summary>
        /// <returns>Enumerator listing the symbols defined in this grammar.</returns>
        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() {
            // Return enumerator on symbols.
            return _Symbols.Values.GetEnumerator();
        }

        /// <summary>
        /// Initialize a grammar by loading a previously stored XML stream containing the state machine required for this
        /// grammar. In case the grammar specification serialized in the XML stream does not match the current grammar, this
        /// finishes the grammar normally.
        /// </summary>
        /// <param name="start">Start symbol to use for generating/loading grammar.</param>
        /// <param name="strm">Stream containing the XML formatted representation of the state machine.</param>
        /// <returns>List of warnings that were encountered while creating grammar.</returns>
        public IEnumerable<string> Finish(string start, Stream strm) {
            // Check whether we're already finalized. When so, no need to redo setup.
            if( _States != null )
                return new List<string>() { "Grammar already finalized, no warnings stored" };

            // Load XML document and fetch toplevel child.
            XmlDocument doc = new XmlDocument();
            doc.Load(strm);
            XmlNode grammar = doc.FirstChild;

            // Check starting symbol.
            if( grammar.Attributes["start"].InnerText != start ) {
                // Invalid start, return normally.
                List<string> warnings = (List<string>)Finish(start);
                warnings.Add("Recreated because start symbol doesn't match XML stream specification");
                return warnings;
            }

            // Walk symbols in document.
            Dictionary<Symbol, XmlNode> ntnodes = new Dictionary<Symbol, XmlNode>();
            HashSet<Symbol> tocheck = new HashSet<Symbol>(_Symbols.Values);
            foreach( XmlNode xmlsymb in grammar.SelectNodes("symbols/symbol") ) {
                // Check whether the symbol exists here and whether it matches.
                Symbol symb;
                if( !_Symbols.TryGetValue(xmlsymb.Attributes["name"].InnerText, out symb) || !symb.CheckXML(xmlsymb) ) {
                    // Symbol doesn't exist, normal finish.
                    List<string> warnings = (List<string>)Finish(start);
                    warnings.Add("Recreated because symbol in XML stream not found or not matched in grammar");
                    return warnings;
                }

                // Add to matched set (now that we know its ID in the store), and to symbol nodes if applicable.
                tocheck.Remove(symb);
                if( !symb.IsTerminal )
                    ntnodes[symb] = xmlsymb;
            }

            // Check whether all symbols were found. If not, just initialize "normally".
            if( tocheck.Count > 0 ) {
                // Not finished, return normally.
                List<string> warnings = (List<string>)Finish(start);
                warnings.Add("Recreated because not all symbols in grammar in XML stream");
                return warnings;
            }

            // Load production id dictionary (checking productions for match).
            Dictionary<Symbol, Dictionary<int, int>> prodids = new Dictionary<Symbol, Dictionary<int, int>>();
            foreach( KeyValuePair<Symbol, XmlNode> symb in ntnodes ) {
                // Create new production dictionary.
                Dictionary<int, int> symbprodids;
                prodids[symb.Key] = symbprodids = new Dictionary<int, int>();

                // Check the productions. In case this fails to match, build grammar "normally".
                if( !symb.Key.CheckProductionsXML(symb.Value, _Symbols, symbprodids) ) {
                    // Production doesn't match, finish normally.
                    List<string> warnings = (List<string>)Finish(start);
                    warnings.Add("Recreated because not all productions for symbol matched");
                    return warnings;
                }
            }

            // Augment symbols (with required extras).
            _Start = _Symbols[start];
            _EOI = _Symbols[""] = new Symbol(this, "");

            // Load states.
            _States = new Dictionary<int, Dictionary<Symbol, StateAction>>();
            foreach( XmlNode xmlstate in grammar.SelectNodes("states/state") ) {
                // Initialize state ID dictionary for current state.
                Dictionary<Symbol, StateAction> act = new Dictionary<Symbol, StateAction>();
                _States[Convert.ToInt32(xmlstate.Attributes["id"].InnerText, CultureInfo.InvariantCulture)] = act;

                // Load actions for state.
                foreach( XmlNode xmlact in xmlstate.SelectNodes("action") )
                    act[_Symbols[xmlact.Attributes["symbol"].InnerText]] = new StateAction(xmlact, _Symbols, prodids);
            }

            // Don't have warnings, return none.
            return new List<string>() { "Loaded grammar from XML file, no warnings stored" };
        }

        /// <summary>
        /// Finish the current grammar, loading the state from the passed stored grammar.
        /// </summary>
        /// <param name="start">Start state to use.</param>
        /// <param name="gram">Stored grammar object.</param>
        /// <returns>List of warnings encountered during grammar finishing.</returns>
        public IEnumerable<string> Finish(string start, IStoredGrammar gram) {
            // Check whether we're already finalized. When so, no need to redo setup.
            if( _States != null )
                return new List<string>() { "Grammar already finalized, no warnings stored" };

            // Check starting symbol.
            if( gram.Start != start ) {
                // Invalid start, return normally.
                List<string> warnings = (List<string>)Finish(start);
                warnings.Add("Recreated because start symbol doesn't match stored machine specification");
                return warnings;
            }

            // Walk over symbols.
            Dictionary<Symbol, Dictionary<int, int>> prodids = new Dictionary<Symbol, Dictionary<int, int>>();
            HashSet<Symbol> tocheck = new HashSet<Symbol>(_Symbols.Values);
            foreach( StoredSymbol storsymb in gram.Symbols ) {
                // Check whether the symbol exists and matches.
                Symbol symb;
                if( storsymb.Name.Length == 0 )
                    // Is EOI; ignore.
                    continue;
                else if( !_Symbols.TryGetValue(storsymb.Name, out symb) ) {
                    // Symbol doesn't exist, normal finish.
                    List<string> warnings = (List<string>)Finish(start);
                    warnings.Add("Recreated because symbol in stored machine not found");
                    return warnings;
                }

                // Create production ID dict and check symbol.
                Dictionary<int, int> prodid = prodids[symb] = new Dictionary<int, int>();
                if( !symb.CheckCS(storsymb, prodid) ) {
                    // Symbol doesn't match, normal finish.
                    List<string> warnings = (List<string>)Finish(start);
                    warnings.Add("Recreated because symbol in stored machine is different");
                    return warnings;
                }

                // Matched; remove from match set.
                tocheck.Remove(symb);
            }

            // Check whether all symbols matched.
            if( tocheck.Count > 0 ) {
                // Not finished, return normally.
                List<string> warnings = (List<string>)Finish(start);
                warnings.Add("Recreated because not all symbols in grammar in stored machine");
                return warnings;
            }

            // Augment symbols (with required extras).
            _Start = _Symbols[start];
            _EOI = _Symbols[""] = new Symbol(this, "");

            // Load states.
            int nextidx = 0;
            _States = new Dictionary<int, Dictionary<Symbol, StateAction>>();
            foreach( Dictionary<StoredSymbol, StoredStateAction> state in gram.States ) {
                // Create state set and load it.
                Dictionary<Symbol, StateAction> acts = _States[nextidx++] = new Dictionary<Symbol, StateAction>();
                foreach( KeyValuePair<StoredSymbol, StoredStateAction> act in state )
                    // Load the action.
                    acts[_Symbols[act.Key.Name]] = new StateAction(act.Value, _Symbols, prodids);
            }

            // Done.
            return new List<string>() { "Loaded grammar from .NET data, no warnings stored" };
        }

        /// <summary>
        /// Finalize the current grammar. Finalizing a grammar builds the state machine for matching it using a stack machine, and
        /// might return a set of warnings that were produced while building the state sets (such as unmatchable symbols). The
        /// specified token is the starting symbol for the grammar. When a grammar has already been finished, this method just
        /// returns the warnings collected during finish.
        /// </summary>
        /// <param name="start">Starting symbol name.</param>
        /// <returns>Enumeration of warning messages that the build process uncovered.</returns>
        public IEnumerable<string> Finish(string start) {
            // Check whether we're already finalized; if so, do nothing.
            if( _States != null )
                return new List<string>() { "Grammar already finalized, no warnings stored" };

            // Check starting symbol.
            if( start == null )
                throw new ArgumentNullException("Trying to finish grammar with null starting symbol");
            else if( !_Symbols.ContainsKey(start) )
                throw new InvalidOperationException("Invalid starting symbol, not found");

            // Initialize required extra symbols.
            _Epsilon = new Symbol(this, "ε");
            _EOI = _Symbols[""] = new Symbol(this, "");

            // Finalize grammar.
            List<string> warnings = new List<string>();
            AugmentGrammar(start, warnings);
            CheckDependencies(warnings);
            CalculateFirst(warnings);
            BuildLRItems(warnings);
            BuildStates(warnings);

            // Clean up non-required locals and set up final start.
            _Epsilon = null;
            _AugmentedSymbols = null;
            _Start = _Symbols[start];
            _FirstSets = null;
            _LRItems = null;
            _Transitions = null;

            // Return list of warnings.
            return warnings;
        }

        /// <summary>
        /// Store the current finished grammar to the specified stream, creating an XML representation of the grammar and its
        /// state machine.
        /// </summary>
        /// <param name="strm">Stream to store grammar to.</param>
        public void StoreXML(Stream strm) {
            // Check whether grammar is finished.
            if( _States == null )
                throw new InvalidOperationException("Trying to store grammar when not finished");

            // Create XML root.
            XmlDocument doc = new XmlDocument();
            XmlNode grammar = doc.AppendChild(doc.CreateElement("grammar"));
            grammar.Attributes.Append(doc.CreateAttribute("start")).InnerText = _Start.Name;

            // Store symbols.
            XmlNode symbols = grammar.AppendChild(doc.CreateElement("symbols"));
            foreach( Symbol symb in _Symbols.Values )
                // Attach symbol if not EOI.
                if( symb.Name.Length > 0 )
                    symbols.AppendChild(symb.StoreXML(doc));

            // Store state machine.
            XmlNode states = grammar.AppendChild(doc.CreateElement("states"));
            foreach( KeyValuePair<int, Dictionary<Symbol, StateAction>> state in _States ) {
                // Create state and attach attributes.
                XmlNode xmlstate = states.AppendChild(doc.CreateElement("state"));
                xmlstate.Attributes.Append(doc.CreateAttribute("id")).InnerText = state.Key.ToString(CultureInfo.InvariantCulture);

                // Create actions.
                foreach( KeyValuePair<Symbol, StateAction> act in state.Value ) {
                    // Create new action target.
                    XmlNode xmlact = xmlstate.AppendChild(doc.CreateElement("action"));
                    xmlact.Attributes.Append(doc.CreateAttribute("symbol")).InnerText = act.Key.Name;

                    // Store state action.
                    act.Value.StoreXML(doc, xmlact);
                }
            }

            // Finalize the XML document.
            doc.Save(strm);
        }

        /// <summary>
        /// Store the current grammar as a C# source file to the specified output.
        /// </summary>
        /// <param name="strm">Stream to store to.</param>
        /// <param name="ns">Namespace to use for grammar.</param>
        /// <param name="name">Name to use for grammar class.</param>
        public void StoreCS(Stream strm, string ns, string name) {
            // Check whether grammar is finished.
            if( _States == null )
                throw new InvalidOperationException("Grammar is not finished, cannot store");

            // Initialize output.
            using( StreamWriter os = new StreamWriter(strm, new UTF8Encoding(false)) ) {
                // Write header (class declaration, constructor, using declarations).
                os.WriteLine("using System;");
                os.WriteLine("using System.Collections.Generic;");
                os.WriteLine("using System.Linq;");
                os.WriteLine("using eu.h8me.Parsing.ParserLib;");
                os.WriteLine("namespace {0} {{ internal sealed class {1} : IStoredGrammar {{", ns, name);
                os.WriteLine("private static {0} SINGLETON = new {0}();", name);
                os.WriteLine("private StoredSymbol[] _Symbols;");
                os.WriteLine("private Dictionary<StoredSymbol, StoredStateAction>[] _States = new Dictionary<StoredSymbol, StoredStateAction>[{0}];", _States.Count);

                // Constructor.
                os.WriteLine("private {0}() {{", name);
                os.WriteLine("Dictionary<string, StoredSymbol> symbs = new Dictionary<string, StoredSymbol>();");
                os.WriteLine("InitializeSymbols(symbs);");
                os.WriteLine("InitializeProductions(symbs);");
                foreach( int state in _States.Keys )
                    os.WriteLine("InitializeState{0}(symbs);", state);
                os.WriteLine("_Symbols = symbs.Values.ToArray<StoredSymbol>();");
                os.WriteLine("}");

                // Symbol storage.
                HashSet<Symbol> prodstore = new HashSet<Symbol>();
                os.WriteLine("private void InitializeSymbols(Dictionary<string, StoredSymbol> symbs) {");
                foreach( Symbol symb in _Symbols.Values ) {
                    // Check whether is a non-terminal; if so, we need to store productions.
                    if( !symb.IsTerminal )
                        prodstore.Add(symb);
                    symb.StoreCS(os);
                }
                os.WriteLine("}");

                // Production storage.
                os.WriteLine("private void InitializeProductions(Dictionary<string, StoredSymbol> symbs) {");
                foreach( Symbol symb in prodstore )
                    symb.StoreProductionsCS(os);
                os.WriteLine("}");

                // State action storage.
                foreach( KeyValuePair<int, Dictionary<Symbol, StateAction>> state in _States ) {
                    // Create method for state.
                    os.WriteLine("private void InitializeState{0}(Dictionary<string, StoredSymbol> symbs) {{", state.Key);
                    os.WriteLine("Dictionary<StoredSymbol, StoredStateAction> acts;");
                    if( state.Value.Count > 0 )
                        os.WriteLine("StoredStateAction act;");

                    // Initialize dictionary for state.
                    os.WriteLine("_States[{0}] = acts = new Dictionary<StoredSymbol, StoredStateAction>();", state.Key);
                    foreach( KeyValuePair<Symbol, StateAction> act in state.Value ) {
                        // Store state (binding it to symbol).
                        act.Value.StoreCS(os);
                        os.WriteLine("acts[symbs[\"{0}\"]] = act;", act.Key.Name);
                    }
                    os.WriteLine("}");
                }

                // Finalize output.
                os.WriteLine("public string Start {{ get {{ return \"{0}\"; }} }}", _Start.Name);
                os.WriteLine("public IEnumerable<StoredSymbol> Symbols { get { return _Symbols; } }");
                os.WriteLine("public IEnumerable<Dictionary<StoredSymbol, StoredStateAction>> States { get { return _States; } }");
                os.WriteLine("public static {0} Singleton {{ get {{ return SINGLETON; }} }}", name);
                os.WriteLine("} }");
            }
        }

        /// <summary>
        /// Build an augmented symbol list, which contains a helper "start" symbol (with only one production).
        /// </summary>
        /// <param name="start">Actual start symbol of the grammar.</param>
        private void AugmentGrammar(string start, List<string> warnings) {
            // Copy list of symbols from symbol dictionary.
            _AugmentedSymbols = new List<Symbol>(_Symbols.Values);

            // Create start symbol.
            _Start = new Symbol(this, "Z");
            _Start.Add(_Symbols[start] + _EOI);
            _AugmentedSymbols.Add(_Start);
        }

        /// <summary>
        /// Build symbol and production dependency tree, enumerating the reduce precedence for non-terminals and finding symbols
        /// that can never be reduced.
        /// </summary>
        private void CheckDependencies(List<string> warnings) {
            // Initialize sets.
            Dictionary<Symbol, bool> reachable = new Dictionary<Symbol, bool>();
            Dictionary<Symbol, HashSet<Symbol>> depends = new Dictionary<Symbol, HashSet<Symbol>>();
            reachable[_Start] = true;

            // Check for unreachable terminals/non-terminals.
            foreach( Symbol symb in _AugmentedSymbols ) {
                // Initialize reachability for this symbol to false.
                if( !reachable.ContainsKey(symb) )
                    reachable[symb] = false;

                // Walk over all production symbols and set the respective symbols to reached.
                foreach( Production prod in symb ) {
                    // Update reachabilities.
                    foreach( Symbol prodsymb in prod )
                        if( prodsymb != symb )
                            reachable[prodsymb] = true;

                    // Check direct dependency on other non-terminal.
                    if( prod.Count == 1 && !prod[0].IsTerminal ) {
                        // Create dependency set if not finished.
                        HashSet<Symbol> dep;
                        if( !depends.TryGetValue(symb, out dep) || dep == null )
                            depends[symb] = dep = new HashSet<Symbol>();

                        // Add the non-terminal symbol to the depends and create respective own key for it if not present.
                        dep.Add(prod[0]);
                        if( !depends.ContainsKey(prod[0]) )
                            depends[prod[0]] = null;
                    }
                }
            }

            // Check for unreachable symbols. EOI is always unreachable, as it only appears as a lookahead token.
            foreach( KeyValuePair<Symbol, bool> reach in reachable )
                if( !reach.Value )
                    warnings.Add(String.Format("Unreachable {0}terminal: {1}", reach.Key.IsTerminal ? "" : "non-", reach.Key));

            // Do a depth first topological sort on the contents.
            int cnt = depends.Count;
            Stack<Symbol> tovisit = new Stack<Symbol>(depends.Keys);
            while( tovisit.Count > 0 ) {
                // Fetch a token.
                Symbol symb = tovisit.Pop();
                HashSet<Symbol> deps;
                if( depends.TryGetValue(symb, out deps) && deps != null && deps.Count > 0 ) {
                    // Has dependencies; clean it from list (and mark as visited).
                    depends.Remove(symb);

                    // Put the element in proper order back on stack.
                    tovisit.Push(symb);
                    foreach( Symbol dep in deps )
                        tovisit.Push(dep);
                } else if( symb.ReducePrecedence == 0 )
                    // Has no more dependencies in stack order (and/or was visited already), but no precedence set up.
                    symb.ReducePrecedence = cnt--;
            }
        }

        /// <summary>
        /// Calculate FIRST sets for all symbols in the current production.
        /// </summary>
        private void CalculateFirst(List<string> warnings) {
            // Loop until first set doesn't change.
            _FirstSets = new Dictionary<Symbol, HashSet<Symbol>>();
            bool changed;
            do {
                // Initialize changed state.
                changed = false;
                foreach( Symbol symb in _AugmentedSymbols ) {
                    // Fetch first set for symbol.
                    HashSet<Symbol> first;
                    if( !_FirstSets.TryGetValue(symb, out first) )
                        _FirstSets[symb] = first = new HashSet<Symbol>();

                    // Check whether this is a terminal; the first of a terminal it itself.
                    if( symb.IsTerminal ) {
                        // Add symbol to first set of symbol.
                        changed |= first.Add(symb);
                        continue;
                    }

                    // Process a non-terminal.
                    foreach( Production prod in symb ) {
                        // Fetch first set of symbols in production recursively. When there are no elements in production,
                        // this production is an epsilon production.
                        bool foundeps = true;
                        foreach( Symbol subsymb in prod ) {
                            // Reset epsilon find and check whether we are adding the same symbol.
                            foundeps = false;
                            if( subsymb == symb ) {
                                // Only check for epsilon find on symbol.
                                if( !first.Contains(_Epsilon) )
                                    break;
                                continue;
                            }

                            // Get production symbol first set, and process only when there is one.
                            HashSet<Symbol> subfirst;
                            if( _FirstSets.TryGetValue(subsymb, out subfirst) ) {
                                // Only process when we already have a subset created.
                                foreach( Symbol subfirstitem in subfirst ) {
                                    if( subfirstitem != _Epsilon )
                                        // First symbol isn't epsilon, just add it verbatim.
                                        changed |= first.Add(subfirstitem);
                                    else
                                        foundeps = true;
                                }
                            }

                            // Check whether we found epsilon in last first set; don't continue with next symbol if not.
                            if( !foundeps )
                                break;
                        }

                        // Check whether we found epsilon also in the last subsymbol of the production; if so, add epsilon as
                        // first of this production.
                        if( foundeps )
                            changed |= first.Add(_Epsilon);
                    }
                }
            } while( changed );
        }

        /// <summary>
        /// Find the FIRST set for a specific list of symbols (symbs), with the specified possible trailing symbol set. This
        /// requires that CalculateFirst() has been run.
        /// </summary>
        /// <param name="symbs">Symbols to calculate FIRST set for.</param>
        /// <param name="trailsymbs">Possible trailing symbols.</param>
        /// <returns>FIRST set for symbol list.</returns>
        private HashSet<Symbol> First(IEnumerable<Symbol> symbs, IEnumerable<Symbol> trailsymbs) {
            // Calculate first set of initial symbol list.
            HashSet<Symbol> first = new HashSet<Symbol>();
            bool foundeps = true;
            foreach( Symbol symb in symbs ) {
                // Walk over firsts of symbol in chain.
                foundeps = false;
                foreach( Symbol subfirstitem in _FirstSets[symb] ) {
                    if( subfirstitem != _Epsilon )
                        // First symbol isn't epsilon, just add it verbatim.
                        first.Add(subfirstitem);
                    else
                        foundeps = true;
                }

                // Check whether we found epsilon in current set; if not, break.
                if( !foundeps )
                    break;
            }

            // Check whether we found epsilon also in the last subsymbol of the symbol list (or the symbol list was empty);
            // if so, add trailing first set.
            if( foundeps )
                first.UnionWith(trailsymbs);

            // Return first set.
            return first;
        }

        /// <summary>
        /// Build the closure of a specified LR item set, adding the items belonging to the closure inplace.
        /// </summary>
        /// <param name="items">LR item set to build the closure for.</param>
        private void Closure(LRItemSet items) {
            // Loop while we have a change.
            do {
                // Attach all productions created by shifting production from current LR items. This ignores those positions where
                // the next symbol is a terminal (because NextSymbol.Count is zero).
                items.ResetState();
                foreach( KeyValuePair<LRItem, SortedDictionary<Symbol, bool>> item in items ) {
                    // Only process when the next symbol is a non-terminal (i.e., we can descend a rule).
                    if( item.Key.HasNextSymbol )
                        for( int i = 0; i < item.Key.NextSymbol.Count; ++i )
                            // Try to add a new LRItem and a new lookahead set for new production.
                            items.Add(new LRItem(item.Key.NextSymbol, i, 0), First(item.Key.ProductionRule.Tail(item.Key.RulePosition), item.Value.Keys));

                    // Check whether set was changed; if so break iteration and restart (because iterator is invalidated).
                    if( items.Changed )
                        break;
                }
            } while( items.Updated );
        }

        /// <summary>
        /// Calculate the GOTO LR item set for the specified LR item set, when using the specified symbol as lookahead.
        /// </summary>
        /// <param name="items">Item set to calculate the GOTO item set for.</param>
        /// <param name="symb">Symbol which is the lookahead.</param>
        /// <returns>LR item set after GOTO operation for which the closure has already been calculated.</returns>
        private LRItemSet Goto(LRItemSet items, Symbol symb) {
            // Build new set of items.
            LRItemSet rv = new LRItemSet();
            foreach( KeyValuePair<LRItem, SortedDictionary<Symbol, bool>> item in items )
                // Check whether next symbol is requested symbol and attach respective item to return value.
                if( item.Key.HasNextSymbol && item.Key.NextSymbol == symb )
                    rv.Add(new LRItem(item.Key.Symbol, item.Key.Production, item.Key.RulePosition + 1), item.Value.Keys);

            // Return closure of resulting items.
            Closure(rv);
            return rv;
        }

        /// <summary>
        /// Build the finite automaton describing the grammar by enumerating the LR item sets that make up the grammar, and
        /// recording their transitions.
        /// </summary>
        private void BuildLRItems(List<string> warnings) {
            // Initialize LR item sets and transitions.
            _LRItems = new Dictionary<LRItemSet, int>();
            _Transitions = new Dictionary<int, Dictionary<Symbol, int>>();

            // Create initial start set and build its closure.
            LRItemSet start = new LRItemSet();
            start.Add(new LRItem(_Start, 0, 0), new HashSet<Symbol>());
            Closure(start);

            // Create state index for initial set.
            int nextitem = START_STATE;
            int startidx = _LRItems[start] = nextitem++;

            // Initialize stack of items to process.
            Stack<object> toprocess = new Stack<object>();
            toprocess.Push(start);
            toprocess.Push(startidx);
            while( toprocess.Count > 0 ) {
                // Fetch an item and create state table.
                int curidx = (int)toprocess.Pop();
                LRItemSet curset = (LRItemSet)toprocess.Pop();
                _Transitions[curidx] = new Dictionary<Symbol, int>();

                // Create LR item sets from all symbols in the item set.
                foreach( Symbol nextsymb in curset.NextSymbols ) {
                    // Create item set and fetch index.
                    LRItemSet newset = Goto(curset, nextsymb);
                    int newidx;
                    if( !_LRItems.TryGetValue(newset, out newidx) ) {
                        // No index present; create new one and enqueue this item so be processed.
                        newidx = _LRItems[newset] = nextitem++;
                        toprocess.Push(newset);
                        toprocess.Push(newidx);
                    }

                    // Create entry in transition table.
                    _Transitions[curidx][nextsymb] = newidx;
                }
            }
        }

        /// <summary>
        /// Build the actual stack machine state sets from the deterministic finite automaton built by BuildLRItems(), and
        /// record shift/reduce errors that are encountered when multiple transitions in one state are possible.
        /// </summary>
        private void BuildStates(List<string> warnings) {
            // Initialize state machine.
            Dictionary<Symbol, HashSet<StateAction>> conflicts = new Dictionary<Symbol, HashSet<StateAction>>();
            _States = new Dictionary<int, Dictionary<Symbol, StateAction>>();
            foreach( KeyValuePair<LRItemSet, int> items in _LRItems ) {
                // Create table for entry.
                Dictionary<Symbol, StateAction> state = _States[items.Value] = new Dictionary<Symbol, StateAction>();
                foreach( KeyValuePair<Symbol, int> trans in _Transitions[items.Value] )
                    // Enter shift/goto action depending on transition symbol (don't need to store which).
                    state[trans.Key] = new StateAction(trans.Value);

                // Check LR items in this item for possible reductions, and add them to state table.
                foreach( KeyValuePair<LRItem, SortedDictionary<Symbol, bool>> item in items.Key ) {
                    if( !item.Key.HasNextSymbol ) {
                        // Create reductions for all lookahead tokens.
                        foreach( Symbol la in item.Value.Keys ) {
                            // Check whether state is already bound.
                            StateAction cur;
                            if( !state.TryGetValue(la, out cur) )
                                // Create it.
                                state[la] = cur = new StateAction();
                            else {
                                // Check type of conflict.
                                if( cur.ReduceActions.Count > 0 )
                                    // At least one reduce action here already.
                                    warnings.Add(String.Format("Reduce/Reduce conflict on {0} in state {1}", la, items.Value));
                                else
                                    // Shift action here already.
                                    warnings.Add(String.Format("Shift/Reduce conflict on {0} in state {1}", la, items.Value));

                                // Attach to list of conflict states.
                                HashSet<StateAction> cstates;
                                if( !conflicts.TryGetValue(la, out cstates) )
                                    conflicts[la] = cstates = new HashSet<StateAction>();
                                cstates.Add(cur);
                            }

                            // Insert new reduce state.
                            cur.ReduceActions.Add(new ReduceAction(item.Key.Symbol, item.Key.Production));
                        }
                    }
                }
            }

            // Walk over conflicts, finalizing them (i.e., resolving them if appropriate).
            foreach( KeyValuePair<Symbol, HashSet<StateAction>> conflict in conflicts )
                foreach( StateAction act in conflict.Value )
                    act.ResolveConflict(conflict.Key, warnings);
        }

        /// <summary>
        /// Create a new parser object for the current grammar, which does not share the state with other parser objects.
        /// Creating a parser object is only possible when the grammar has been finished.
        /// </summary>
        public Parser Parser {
            get {
                // Return parser when finished.
                if( _States == null )
                    throw new InvalidOperationException("Trying to get parser when not finished");
                return new Parser(this, START_STATE);
            }
        }

        /// <summary>
        /// Invoke the grammar wide merge event for the specified ambiguous production.
        /// </summary>
        /// <param name="parser">Parser that is invoking the merge event.</param>
        /// <param name="symb">Symbol that is being merged to.</param>
        /// <param name="data1">First calculated reduction.</param>
        /// <param name="data2">Second calculated reduction.</param>
        /// <param name="lex">Current token that was read before merge.</param>
        /// <returns>Value to use for the merged reduction path.</returns>
        internal object Merge(Parser parser, Symbol symb, StateLink data1, StateLink data2, Token lex) {
            // Check whether merge event is set up.
            if( _MergeEvent != null )
                return _MergeEvent(new MergeState(this, parser, symb, data1.Production, data2.Production), data1.Token.Data, data2.Token.Data);

            // No merge event available, signal that.
            throw new MergeFailedException(String.Format("Failed to find merge event for {0} (prod {1}, {2}), no global merge event available, parse failed", symb, data1.ProductionRule, data2.ProductionRule), lex);
        }

    }

}
